package com.ftg.learn.chapter09.settest;

/**
 * 删除倒数第N个节点
 * 编写一个函数，接受一个链表（用ListNode表示）和一个整数N，删除链表倒数第N个节点。
 *
 * @author lijiaxin
 * @version 1.0
 * @date 2023/8/17 8:23
 */

public class ListNode {

    private ListNode next;

    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode pre = head;
        int last = length(head) - n;
        //如果last等于0表示删除的是头结点
        if (last == 0) {
            return head.next;
        }
        //这里首先要找到要删除链表的前一个结点
        for (int i = 0; i < last - 1; i++) {
            pre = pre.next;
        }
        //然后让前一个结点的next指向要删除节点的next
        pre.next = pre.next.next;
        return head;
    }

    //求链表的长度
    private int length(ListNode head) {
        if (head==null) {
            return 0;
        }
        return length(head.next)+1;
    }

}

